﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Swift
{
    public static class SwiftEx
    {
        // 查找子串
        public static int IndexOfSub<T>(this T[] fullArr, T[] subArr)
        {
            int KMPSearch(T[] arr, T[] sub, int[] next)
            {
                int M = arr.Length;
                int N = sub.Length;
                int i = 0;
                int j = 0;
                while (i < M && j < N)
                {
                    if (j == -1 || arr[i].Equals(sub[j]))
                    {
                        i++;
                        j++;
                    }
                    else
                    {
                        j = next[j];
                    }
                }
                if (j == N)
                    return i - j;
                else
                    return -1;
            }

            void getNext(T[] sub, int[] next)
            {
                int N = sub.Length;
                next[0] = -1;
                int k = -1;
                int j = 0;
                while (j < N - 1)
                {
                    if (k == -1 || sub[j].Equals(sub[k]))
                    {
                        ++k;
                        ++j;
                        next[j] = k;
                    }
                    else
                        k = next[k];
                }
            }

            int[] indexArr = new int[subArr.Length];
            getNext(subArr, indexArr);
            return KMPSearch(fullArr, subArr, indexArr);
        }
    }
}
